'''
给一个二维列表,表示迷宫(0表示通道,1表示围墙).给出算法,求一条走出迷宫的路径

'''

maze = [
    [1,1,1,1,1,1,1,1,1,1],
    [1,0,0,1,0,0,0,1,0,1],
    [1,0,0,1,0,0,0,1,0,1],
    [1,0,0,0,0,1,1,0,0,1],
    [1,0,1,1,1,0,0,0,0,1],
    [1,0,0,0,1,0,0,0,0,1],
    [1,0,1,0,0,0,1,0,0,1],
    [1,0,1,1,1,0,1,1,0,1],
    [1,1,0,0,0,0,0,0,0,1],
    [1,1,1,1,1,1,1,1,1,1]
]

'''
栈--深度优先搜索
回溯法
    思路:从一个节点开始,任意找下一个能走的点,当找不到能走的点时,退回上一个点寻找是否有其他方向的点
    使用栈存储当前路径
'''
dirs = [
    lambda x,y:(x+1,y),
    lambda x,y:(x-1,y),
    lambda x,y:(x,y+1),
    lambda x,y:(x,y-1),
]

def maze_path(x1,y1,x2,y2):
    stack = []
    stack.append(x1,y1)
    while len(stack) > 0:
        curNode = stack[-1]  # 当前的结点
        if curNode == (x2,y2):
            # 走到终点了
            for p in stack:
                print(p)
            return
        # x,y 四个方向
        for dir in dirs:
            nextNode = dir(curNode[0],curNode[1])
            # 如果下一个结点能走
            if maze[nextNode[0]][nextNode[1]] == 0:
                stack.append(nextNode)
                maze[nextNode[0]][nextNode[1]] = 2 #2表示该位置已经走过了
                break
        else:
            maze[nextNode[0]][nextNode[1]] = 2
            stack.pop()
    else:
        print('没有路')
        return False
